public class Test {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode n2= new ListNode(2);
        ListNode n3= new ListNode(3);
        ListNode n4= new ListNode(4);
        ListNode n5= new ListNode(5);
        head.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        ListNode node1 = reverseList(head);
        System.out.println(node1.toString());

    }

    // 题目1：反转链表
    public static ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        ListNode curNext = null;
        while(cur != null){
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public ListNode reverseList1(ListNode head) {
        ListNode prve = null;
        ListNode curr = head;
        ListNode curNext = null;
        while(curr != null){
            curNext = curr.next;
            curr.next = prve;
            prve = curr;
            curr = curNext;
        }
        return prve;
    }

    // 题目2：链表的中间结点
    // 如果有两个中间节点，返回第二个。这里的话，只要快慢指针的起始位置在第一个结点。
    // 如果想返回的是第一个，让快慢指针的起始位置在哑节点处即可。
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 题目3：删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode slow  = dummyNode;
        ListNode fast = head;
        while(n > 0){
            fast = fast.next;
            n--;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        slow.next = cur.next;
        cur.next = null;
        return dummyNode.next;
    }

    // 题目4：环形链表
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

}
